package bintree.leetcode;

/**
 * 二叉树的最长路径问题
 * @author yuisama
 * @date 2022/02/22 11:16
 **/
public class Num543_DiameterOfBinaryTree {
    int res = 0;
    // 每一条二叉树的直径长度，就是当前节点的左右子树高度之和(过当前节点)
    // 整棵树的最大直径，不一定都要过根节点，子树中的直径长度有可能 >= 过根节点的所有直径长度
    // 因此这个问题转化为在后序位置，求当前树根直径长度时，顺带计算下最大直径
    public int diameterOfBinaryTree(TreeNode root) {
        traverse(root);
        return res;
    }
    /**
     * 以root为根的二叉树中求二叉树的高度
     * @param root
     * @return
     */
    public int traverse(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftLength = traverse(root.left);
        int rightLength = traverse(root.right);
        // 后序位置
        // 在求二叉树最大高度的时候顺便求最大直径，因为最大直径有可能不过当前根节点
        res = Math.max(res,leftLength + rightLength);
        // 当前节点高度
        return 1 + Math.max(leftLength,rightLength);
    }
}
